#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node {
    int data;
    struct node *next;
    struct node *pre;
}node, *link;

link createNode(int value) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    newNode->pre  = NULL;
    return newNode;
}


void initNode(link *head) {
    link newNode = createNode(0);
    if (newNode == NULL) return;
    *head = newNode;
}

void insertHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->pre = head;
    newNode->next = head->next;

    if (head->next != NULL) {
        head->next->pre = newNode;
    }
    head->next = newNode;
}

void insertTail(link head, int value) {
    link cur = head;
    while(cur->next != NULL) {
        cur = cur->next;
    }
    link newNode = createNode(value);
    if (newNode == NULL) return;

    cur->next = newNode;
    newNode->pre = cur;
}

void printList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    while(cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void delByPos(link head, int pos) {
    if (pos < 1 || head == NULL || head->next == NULL) return;
    int idx = 1;
    link cur = head->next;
    while(cur != NULL && idx < pos) {
        cur = cur->next;
        idx ++;
    }
    if (cur == NULL) return;

    if (cur->pre != NULL) {
        cur->pre->next = cur->next;
    }
    if (cur->next != NULL) {
        cur->next->pre = cur->pre;
    }
    free(cur);
}

void destroy(link *head) {
    if (*head == NULL || (*head)->next == NULL) return;
    link cur = (*head)->next;
    while( cur != NULL) {
        link temp = cur->next;
        free(cur);
        cur = temp;
    }

    (*head)->next = NULL;
}

// 得到链表长度
int getLength(link head) {
    int lenght = 0;
    if (head == NULL || head->next == NULL) return 0;
    link cur = head->next;
    while (cur != NULL) {
        cur = cur->next;
        lenght++;
    }
    return lenght;
}

void reverseList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    head->next = NULL;
    while (cur != NULL) {
        link temp = cur->next;
        cur->next = head->next;
        cur->pre = head;
        if (head->next != NULL) {
            head->next->pre = cur;
        }
        head->next = cur;
        cur = temp;
    }
}

void translate(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    translate(head->next);
    printf("value is %d\n", cur->data);
}

void printAndFreeInOrder(link head) {
    if (head == NULL || head->next == NULL) return;
    while (head->next != NULL) {
        link cur = head->next;
        link minNode = cur;
        while (cur->next != NULL) {
            if (minNode->data > cur->next->data) {
                minNode = cur->next;
                cur = cur->next;
            } else {
                cur = cur->next;
            }
        }
        // 打印最小值
        printf("value is %d\n", minNode->data);

        if (minNode->pre != NULL) {
            minNode->pre->next = minNode->next;
        }
        if (minNode->next != NULL) {
            minNode->next->pre = minNode->pre;
        }
        free(minNode);
    }
}

bool isDesc(link head) {
    if (head == NULL || head->next == NULL) return false;
    link cur = head->next;
    if (cur->next != NULL) {
        if (cur->data > cur->next->data) {
            return true;
        } else {
            return false;
        }
    } else {
        return true;
    }

}

// 将两个有序的的链表，合并为一个降序的链表
link mergeDecreasingReuseHead(link la, link lb) {
    bool flagA = isDesc(la);
    bool flagB = isDesc(lb);
    if (!flagA) {
        reverseList(la);
    }

    if (!flagB) {
        reverseList(lb);
    }

    link pa = la->next;
    link pb = lb->next;
    link result = NULL;
    initNode(&result);
    link tail = result;
    while (pa != NULL && pb != NULL) {
        if (pa->data >= pb->data) {
            link temp = pa->next;
            tail->next = pa;
            pa->pre = tail;
            pa->next = NULL;
            tail = pa;
            pa = temp;
        } else {
            link temp = pb->next;
            tail->next = pb;
            pb->pre = tail;
            pb->next = NULL;
            tail = pb;
            pb = temp;
        }
    }

    while (pa) {
        link temp = pa->next;
        tail->next = pa;
        pa->pre = tail;
        pa->next = NULL;
        tail = pa;
        pa = temp;
    }

    while (pb) {
        link temp = pb->next;
        tail->next = pb;
        pb->pre = tail;
        pb->next = NULL;
        tail = pb;
        pb = temp;
    }

    return result;
}

// 从两个有序的链表重找出公共数据，形成新的链表
link getCommonEle(link la, link lb) {
    if (la == NULL || la->next == NULL) return NULL;
    if (lb == NULL || lb->next == NULL) return NULL;

    link result = NULL;
    initNode(&result);
    link tail = result;

    link pa = la->next;
    link pb = lb->next;

    while (pa != NULL && pb != NULL) {
        if (pa->data < pb->data) {
            pa = pa->next;
        } else if (pa->data > pb->data) {
            pb = pb->next;
        } else {
            link newNode = createNode(pa->data);
            if (newNode == NULL) {
                // 这里也可以加清理逻辑，避免内存泄漏
                return NULL;
            }
            tail->next = newNode;
            newNode->pre = tail;
            tail = newNode;

            pa = pa->next;
            pb = pb->next;
        }
    }

    // 处理无交集的情况
    if (result->next == NULL) {
        free(result);
        return NULL;
    }

    return result;
}


bool findSubsequence(link la, link lb) {
    if (la == NULL || la->next == NULL) return NULL;
    if (lb == NULL || lb->next == NULL) return NULL;

    link pa = la->next;
    link pb = lb->next;

    while (pa) {
        link paa = pa;
        while (pb) {
            if (paa->data == pb->data) {
                paa = paa->next;
                pb = pb->next;
            } else {
                break;
            }
        }

        if (pb == NULL) {
            return true;
        }

        pa = pa->next;
    }
}

//保留两个升序链表的交集元素，并释放非交集部分内存（链表1被就地修改）
void findIntersection(link la, link lb) {
    if (la == NULL || la->next == NULL || lb == NULL || lb->next == NULL) return;

    link pa = la->next;
    link pb = lb->next;

    while (pa != NULL && pb != NULL) {
        if (pa->data == pb->data) {
            pa = pa->next;
            pb = pb->next;
        } else if (pa->data < pb->data) {
            // 删除不在交集中的节点
            link temp = pa->next;
            pa->pre->next = pa->next;
            if (pa->next != NULL)
                pa->next->pre = pa->pre;
            free(pa);
            pa = temp;
        } else { // pa->data > pb->data
            pb = pb->next;
        }
    }

    // 删除 pa 剩下的节点（pb 已到尾）
    while (pa != NULL) {
        link temp = pa->next;
        pa->pre->next = pa->next;
        if (pa->next != NULL)
            pa->next->pre = pa->pre;
        free(pa);
        pa = temp;
    }

    // 修复头结点 next（若链表清空了）
    if (la->next != NULL && la->next->pre != la) {
        la->next = NULL;
    }
}

link findCommonNode(link la, link lb) {
    if (la == NULL || la->next == NULL || lb == NULL || lb->next == NULL) return NULL;
    int lengA = getLength(la);
    int lengB = getLength(lb);
    int dif = lengA - lengB;

    link pa = la->next;
    link pb = lb->next;
    if (dif > 0) {
        while (dif --) pa = pa->next;
    } else {
        while (dif ++) pb = pb->next;
    }

    while (pa != NULL && pb != NULL) {
        if (pa == pb) return pa;
        pa = pa->next;
        pb = pb->next;
    }

    return NULL;
}


// 将head 按照位置的 奇数和偶数，进行区分，偶数放到 evenHead中，奇数放到 head中
void devideLink(link head, link evenHead) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    link oddTail = head;
    link evenTail = evenHead;
    int idx = 1;

    while (cur != NULL) {
        link temp = cur->next;
        if (idx & 1) {
            oddTail->next = cur;
            cur->pre = oddTail;
            oddTail = cur;
        } else {
            evenTail->next = cur;
            cur->pre = evenTail;
            evenTail = cur;
        }
        cur = temp;
        idx ++;
    }
    if (oddTail->next != NULL) {
        oddTail->next = NULL;
    }
    if (evenTail->next != NULL) {
        evenTail->next = NULL;
    }
}


void delMulMinValue (link head) {
    if (head == NULL || head->next == NULL) return;
    // 找到最小值
    link cur = head->next;
    int minNode = cur->data;
    while (cur != NULL) {
        if (cur->data < minNode) {
            minNode = cur->data;
        }
        cur = cur->next;
    }

    link tempCur = head->next;
    while (tempCur != NULL) {
        link next = tempCur->next;
        if (tempCur->data == minNode) {
            if (tempCur->next != NULL) {
                tempCur->next->pre = tempCur->pre;
            }
            if (tempCur->pre != NULL) {
                tempCur->pre->next = tempCur->next;
            }
            free(tempCur);
            tempCur = next;
        } else {
            tempCur = tempCur->next;
        }
    }
}

void delScope(link head, int left, int right) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    while (cur != NULL) {
        link next = cur->next;
        if (cur->data >= left && cur->data <= right) {
            if (cur->next != NULL) {
                cur->next->pre = cur->pre;
            }
            if (cur->pre != NULL) {
                cur->pre->next = cur->next;
            }
            free(cur);
        }
        cur = next;
    }
}


int main() {

    /**
    link head = NULL;
    initNode(&head);
    insetTail(head, 1);
    insetTail(head, 2);
    insetTail(head, 3);

     *printList(head);
     reverseList(head);
     printList(head);
     printAndFreeInOrder(head);


    link head1 = NULL;
    initNode(&head1);
    insetTail(head1, 3);
    insetTail(head1, 5);
    insetTail(head1, 6);

    // printf("===================================\n");
    // link result = mergeDecreasingReuseHead(head,head1);
    // printList(result);

    /**
    printf("----------------------------------------------\n");
    link commonLink = getCommonEle(head, head1);
    if (commonLink != NULL) {
        printList(commonLink);
    }

    bool flag = findSubsequence(head, head1);
    if (flag) {
        printf("head1 is head's sequence\n");
    } else {
        printf("head1 is not head's sequence\n");
    }

    findIntersection(head, head1);
    printList(head);
    return 0;


    // 初始化两个链表（带头结点）
    link head1 = NULL, head2 = NULL;
    initNode(&head1);
    initNode(&head2);

    // 创建公共部分链表：6 → 7
    link common = createNode(6);
    common->next = createNode(7);

    // 构造链表1：1 → 2 → 3 → 6 → 7
    insertHead(head1, 3);
    insertHead(head1, 2);
    insertHead(head1, 1);

    link p = head1;
    while (p->next != NULL) p = p->next;
    // p->next = common;  // 接入公共部分

    // 构造链表2：4 → 5 → 6 → 7
    link node5 = createNode(5);
    node5->next = common;
    link node4 = createNode(4);
    node4->next = node5;
    head2->next = node4;  // 接入链表2

    // 打印两个链表
    printf("List 1:\n");
    printList(head1);

    printf("List 2:\n");
    printList(head2);

    // 查找第一个公共节点
    link commonNode = findCommonNode(head1, head2);
    if (commonNode) {
        printf("First common node value: \n");
    } else {
        printf("No common node found.\n");
    }
    **/

    link head = NULL;
    link evenHead = NULL;
    initNode(&head);
    initNode(&evenHead);

    insertTail(head, 1);
    insertTail(head, 3);
    insertTail(head, 2);
    printList(head);
    printAndFreeInOrder(head);

    // devideLink(head, evenHead);
    // delMulMinValue(head);
    // delScope(head, 1, 2);
    printList(head);

    return 0;
}